COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	tower.226[w83,jmc]		blocks and towers and traffic lights
C00012 ENDMK
C⊗;
tower.226[w83,jmc]		blocks and towers and traffic lights

	This is a writeup of the 1983 Feb 8 class discussion in
CS226 about a possible term project involving formalizing the
blocks world and including a discussion of building towers.


Basic ontology:

	In this discussion we go a bit beyond Quine's proposal
that the ontology is given by specifying the ranges of the
bound variables.  We also include in it the constants, including
function and predicate constants.  Perhaps he would include them.

	The basic objects are blocks and a table.  The table
may be regarded as a kind of immovable block that can have
many other blocks on it.

	The basic relation is  on(x,y).  If we were to make a purely
static formulation we could take  on  as a predicate and
just write  on(x,y).  Since we are going to use a situation calculus
to represent change, we write either  on(x,y,s)  or  holds(on(x,y),s).

Of course, we can have both.  If our theorem prover knows enough to
distinguish the two uses of  on, we could write the axiom connecting
them as

	∀x y s.on(x,y,s) ≡ holds(on(x,y),s).

If its syntax is more pedantic, we write

	∀x y s.on1(x,y,s) ≡ holds(on2(x,y),s).

In this writeup, I'll assume that the reader can make the distinctions,
and I'll use  on  both as a predicate of three arguments and as
a function of two.  When it is used as a function, its value  on(x,y)
has to be an entity that can "hold" in a situation.  We can use
whatever name we like for such entities.  Suppose we call them
propositions, although situations aren't the same as the possible
worlds of "First order theories ...".

	Besides blocks, it may be convenient to have places, and we
will consider  top(x),  where  x  is a block to be a place.  We
have the axioms

	∀x y.at(x,top(y)) = on(x,y)

or

	∀x y s.at(x,top y,s) ≡ on(x,y,s).

Side remark: The above use of  at  and  top  is like the Japanese use of a
general purpose preposition of location "ni" meaning "at" and nouns for
the locations corresponding to the different prepositions of English.
Thus instead of "The block is on the table", Japanese calls for something
like "The block is at the table's top -  "Tsumiki wa teberu no ue ni arimasu".

	Naturally, blocks and other object can have other associated
parts where things can be located.

	We shall also introduce colors and suppose that the color of
a block depends on the situation.  We write  color(x,s)  for the color
of block  x  in situation  s.  We may also want  color(x)  and
write

	∀x s.color(x,s) = value(color x,s).

Again for variety, we have

	red(x,s) ≡ color(x,s) = red

		 ≡ holds(red x,s)

		 ≡ holds(equal(color x,red),s).

It isn't immediately clear which of these notations will be most useful.

	When we consider motion, there is also a variety of reasonable
first order formalisms.  The simplest writes

	s' = move(x,y,s)

for the situation that results from moving block  x  onto block  y.
We also write  result(move(x,y),s)  for this situation.  If there
may be more than one actor, we may have to write

	s' = result(does(Robby,move(x,y)),s).

Using locations suggests that  move  have a location as its second
argument, so that we have

	s' = result(move(x, top y),s),

where we drop the actor parameter, since we'll have only one actor
in this discussion.


	The other action is coloring: We can have the actions
redden(x)  or  paint(x,color)  and hence can write synonymously
	
	s' = redden(x,s)

	s' = result(redden x, s)

	s' = paint(x,red,s)

	s' = result(paint(x,red),s).



Advanced ontology:

	That was the basic ontology.  In our "advanced ontology"
we will include towers, i.e. constructions made from blocks.
Suppose that we wish to define a traffic light as consisting of
a red block on a green block on a brown block on the table.
We can write

	traffic-light(x,y,z,s) ≡ red(x,s) ∧ green(y,s) ∧ brown(z,s)
		∧ on(x,y,s) ∧ on(y,z,s) ∧ on(z,Table,s)

or

	traffic-light(x,y,z) = red x and green y and brown z
		and on(x,y) and on(y,z) and on(z,Table),

where these are related by

	∀x y z s. traffic-light(x,y,z,s) ≡ holds(traffic-light(x,y,z),s).

This requires the conjunction  and  for combining propositions.

	However, the above traffic-light predicate and function aren't
good enough to express what we need for two reasons:

	1. We may have traffic lights involving different numbers
of blocks, and we want to call them all traffic lights.  Therefore,
we need to be able to denote a traffic light by a single term.

	2. We need traffic light designs.  Thus we may want
to consider (red green black black black) and (red green brown brown)
as two traffic light designs independent of whether traffic lights
with that particular specification are present in a give scene.

	We need to be able to say that a given traffic light design is
realized in the situation s and also to be able to say that one traffic
light design is better than another.

	One possibility is to represent both tower designs and
towers as lists and to use the LISP functions car, cdr and  cons
for operating on these lists.  An tower design might be
(red green brown brown), and one tower would be (A B C D)
where  A, B, C  and  D  are names of blocks.

	The second possibility is to represent both tower designs and
towers as abstract objects, and let the lists mentioned above be
functions of the tower.  Thus we might have

	structure(T1) = (red green brown brown)

and remain non-commital as to whether  T1  has other properties than
its structure.  I suppose that if we can't think of useful or interesting
other properties, we might as well regard towers as lists.

	Another issue is whether we want a tower to maintain its identity
if one of its faces is painted.  In this case, we need the function
structure(T1,s).  Most likely we shall want both concepts - the
tower that retains its identity through some transformations, and
the structure its 

WARNING: I'm printing this for the class of 1983 Feb 10 even though
it is very incomplete so as to provide some record of what was
discussed Feb 8.  Not all of the above ideas need be incorporated
in the term paper.